SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Johnson's algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Johnson's algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For the scheduling algorithm of the same name, see <a href="Job_shop_scheduling" class="mw-redirect" title="Job shop scheduling">Job shop scheduling</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><caption class="infobox-title">Johnson's algorithm</caption><tbody><tr><th scope="row" class="infobox-label">Class</th><td class="infobox-data"><a href="All-pairs_shortest_path_problem" class="mw-redirect" title="All-pairs shortest path problem">All-pairs shortest path problem</a> (for weighted graphs)</td></tr><tr><th scope="row" class="infobox-label">Data structure</th><td class="infobox-data"><a href="Graph_(data_structure)" class="mw-redirect" title="Graph (data structure)">Graph</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="Time_complexity" title="Time complexity">performance</a></th><td class="infobox-data"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|^{2}\log |V|+|V||E|)}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|^{2}\log |V|+|V||E|)}</annotation>

</semantics>

</math></span><img src="./fb710833bfcdc985b76d7594d0e7998c182dabe9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.535ex; height:3.343ex;" alt="{\displaystyle O(|V|^{2}\log |V|+|V||E|)}" loading="lazy"></span></td></tr></tbody></table>

<p><b>Johnson's algorithm</b> is a way to find the <a href="Shortest_path" class="mw-redirect" title="Shortest path">shortest paths</a> between <a href="All-pairs_shortest_path_problem" class="mw-redirect" title="All-pairs shortest path problem">all pairs of vertices</a> in an <a href="Weighted_graph" class="mw-redirect" title="Weighted graph">edge-weighted</a> <a href="Directed_graph" title="Directed graph">directed graph</a>. It allows some of the edge weights to be <a href="Negative_number" title="Negative number">negative numbers</a>, but no negative-weight <a href="Cycle_(graph_theory)" title="Cycle (graph theory)">cycles</a> may exist. It works by using the <a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford algorithm</a> to compute a transformation of the input graph that removes all negative weights, allowing <a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a> to be used on the transformed graph.<sup id="cite_ref-clrs_1-0" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-black_2-0" class="reference"><a href="#cite_note-black-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> It is named after <a href="Donald_B._Johnson" title="Donald B. Johnson">Donald B. Johnson</a>, who first published the technique in 1977.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>A similar reweighting technique is also used in a version of the successive shortest paths algorithm for the <a href="Minimum_cost_flow" class="mw-redirect" title="Minimum cost flow">minimum cost flow</a> problem due to Edmonds and Karp,<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> as well as in <a href="Suurballe's_algorithm" title="Suurballe's algorithm">Suurballe's algorithm</a> for finding two disjoint paths of minimum total length between the same two vertices in a graph with non-negative edge weights.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm_description">Algorithm description</h2></div>

<p>Johnson's algorithm consists of the following steps:<sup id="cite_ref-clrs_1-1" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-black_2-1" class="reference"><a href="#cite_note-black-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<ol><li>First, a new <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">node</a> <span class="texhtml mvar" style="font-style:italic;">q</span> is added to the graph, connected by zero-weight <a href="Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">edges</a> to each of the other nodes.</li>

<li>Second, the <a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford algorithm</a> is used, starting from the new vertex <span class="texhtml mvar" style="font-style:italic;">q</span>, to find for each vertex <span class="texhtml mvar" style="font-style:italic;">v</span> the minimum weight <span class="texhtml"><i>h</i>(<i>v</i>)</span> of a path from <span class="texhtml mvar" style="font-style:italic;">q</span> to <span class="texhtml mvar" style="font-style:italic;">v</span>. If this step detects a negative cycle, the algorithm is terminated.</li>

<li>Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from <span class="texhtml mvar" style="font-style:italic;">u</span> to <span class="texhtml mvar" style="font-style:italic;">v</span>, having length <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(u,v)}</annotation>

</semantics>

</math></span><img src="./c820425919af804281a4d42c9798951ba8f76140.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.965ex; height:2.843ex;" alt="{\displaystyle w(u,v)}" loading="lazy"></span>⁠</span>, is given the new length <span class="texhtml"><i>w</i>(<i>u</i>,<i>v</i>) + <i>h</i>(<i>u</i>) − <i>h</i>(<i>v</i>)</span>.</li>

<li>Finally, <span class="texhtml mvar" style="font-style:italic;">q</span> is removed, and <a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a> is used to find the shortest paths from each node <span class="texhtml mvar" style="font-style:italic;">s</span> to every other vertex in the reweighted graph. The distance in the original graph is then computed for each distance <span class="texhtml mvar" style="font-style:italic;">D</span>(<span class="texhtml mvar" style="font-style:italic;">u</span>, <span class="texhtml mvar" style="font-style:italic;">v</span>), by adding <span class="texhtml mvar" style="font-style:italic;"><i>h</i>(<i>v</i>) − <i>h</i>(<i>u</i>)</span> to the distance returned by Dijkstra's algorithm.</li></ol>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>The first three stages of Johnson's algorithm are depicted in the illustration below.

</p>

<p>The graph on the left of the illustration has two negative edges, but no negative cycles. The center graph shows the new vertex <span class="texhtml mvar" style="font-style:italic;">q</span>, a shortest path tree as computed by the Bellman–Ford algorithm with <span class="texhtml mvar" style="font-style:italic;">q</span> as starting vertex, and the values <span class="texhtml"><i>h</i>(<i>v</i>)</span> computed at each other node as the length of the shortest path from <span class="texhtml mvar" style="font-style:italic;">q</span> to that node. Note that these values are all non-positive, because <span class="texhtml mvar" style="font-style:italic;">q</span> has a length-zero edge to each vertex and the shortest path can be no longer than that edge. On the right is shown the reweighted graph, formed by replacing each edge weight <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w(u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w(u,v)}</annotation>

</semantics>

</math></span><img src="./c820425919af804281a4d42c9798951ba8f76140.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.965ex; height:2.843ex;" alt="{\displaystyle w(u,v)}" loading="lazy"></span>⁠</span> by <span class="texhtml"><i>w</i>(<i>u</i>,<i>v</i>) + <i>h</i>(<i>u</i>) − <i>h</i>(<i>v</i>)</span>. In this reweighted graph, all edge weights are non-negative, but the shortest path between any two nodes uses the same sequence of edges as the shortest path between the same two nodes in the original graph. The algorithm concludes by applying Dijkstra's algorithm to each of the four starting nodes in the reweighted graph.

</p>

<div class="mw-heading mw-heading2"><h2 id="Correctness">Correctness</h2></div>

<p>In the reweighted graph, all paths between a pair <span class="texhtml mvar" style="font-style:italic;">s</span> and <span class="texhtml mvar" style="font-style:italic;">t</span> of nodes have the same quantity <span class="texhtml"><i>h</i>(<i>s</i>) − <i>h</i>(<i>t</i>)</span> added to them. The previous statement can be proven as follows: Let <span class="texhtml mvar" style="font-style:italic;">p</span> be an <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s-t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s-t}</annotation>

</semantics>

</math></span><img src="./e8f385419e3b33f77328af12a164770bec2347bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.77ex; height:2.176ex;" alt="{\displaystyle s-t}" loading="lazy"></span>⁠</span> path. Its weight W in the reweighted graph is given by the following expression:

</p><p><span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(w(s,p_{1})+h(s)-h(p_{1})\right)+\left(w(p_{1},p_{2})+h(p_{1})-h(p_{2})\right)+...+\left(w(p_{n},t)+h(p_{n})-h(t)\right).}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(w(s,p_{1})+h(s)-h(p_{1})\right)+\left(w(p_{1},p_{2})+h(p_{1})-h(p_{2})\right)+...+\left(w(p_{n},t)+h(p_{n})-h(t)\right).}</annotation>

</semantics>

</math></span></span>

</p><p>Every <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle +h(p_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle +h(p_{i})}</annotation>

</semantics>

</math></span><img src="./5d12c8009ff6081cf94762595990d06a1d5d01e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.926ex; height:2.843ex;" alt="{\displaystyle +h(p_{i})}" loading="lazy"></span> is cancelled by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -h(p_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -h(p_{i})}</annotation>

</semantics>

</math></span><img src="./30c64b06af5cbdc28ee807922192971ecf4bcff9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.926ex; height:2.843ex;" alt="{\displaystyle -h(p_{i})}" loading="lazy"></span> in the previous bracketed expression; therefore, we are left with the following expression for <i>W</i>:

</p><p><span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(w(s,p_{1})+w(p_{1},p_{2})+\cdots +w(p_{n},t)\right)+h(s)-h(t)}">

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(w(s,p_{1})+w(p_{1},p_{2})+\cdots +w(p_{n},t)\right)+h(s)-h(t)}</annotation>

</semantics>

</math></span></span>

</p><p>The bracketed expression is the weight of <i>p</i> in the original weighting.

</p><p>Since the reweighting adds the same amount to the weight of every <span class="nowrap">⁠<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s-t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s-t}</annotation>

</semantics>

</math></span><img src="./e8f385419e3b33f77328af12a164770bec2347bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.77ex; height:2.176ex;" alt="{\displaystyle s-t}" loading="lazy"></span>⁠</span> path, a path is a shortest path in the original weighting if and only if it is a shortest path after reweighting. The weight of edges that belong to a shortest path from <i>q</i> to any node is zero, and therefore the lengths of the shortest paths from <i>q</i> to every node become zero in the reweighted graph; however, they still remain shortest paths. Therefore, there can be no negative edges: if edge <i>uv</i> had a negative weight after the reweighting, then the zero-length path from <i>q</i> to <i>u</i> together with this edge would form a negative-length path from <i>q</i> to <i>v</i>, contradicting the fact that all vertices have zero distance from <i>q</i>. The non-existence of negative edges ensures the optimality of the paths found by Dijkstra's algorithm. The distances in the original graph may be calculated from the distances calculated by Dijkstra's algorithm in the reweighted graph by reversing the reweighting transformation.<sup id="cite_ref-clrs_1-2" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Analysis">Analysis</h2></div>

<p>The <a href="Time_complexity" title="Time complexity">time complexity</a> of this algorithm, using <a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci heaps</a> in the implementation of Dijkstra's algorithm, is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|^{2}\log |V|+|V||E|)}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|^{2}\log |V|+|V||E|)}</annotation>

</semantics>

</math></span><img src="./fb710833bfcdc985b76d7594d0e7998c182dabe9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.535ex; height:3.343ex;" alt="{\displaystyle O(|V|^{2}\log |V|+|V||E|)}" loading="lazy"></span>: the algorithm uses <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V||E|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V||E|)}</annotation>

</semantics>

</math></span><img src="./2d81aded51fae699d4f659fee1faa684233ab581.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.733ex; height:2.843ex;" alt="{\displaystyle O(|V||E|)}" loading="lazy"></span> time for the Bellman–Ford stage of the algorithm, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|\log |V|+|E|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|\log |V|+|E|)}</annotation>

</semantics>

</math></span><img src="./f053fdfa75a22bf593bfbac6cf09eff0ab8d64d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.4ex; height:2.843ex;" alt="{\displaystyle O(|V|\log |V|+|E|)}" loading="lazy"></span> for each of the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |V|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |V|}</annotation>

</semantics>

</math></span><img src="./9ddcffc28643ac01a14dd0fb32c3157859e365a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.081ex; height:2.843ex;" alt="{\displaystyle |V|}" loading="lazy"></span> instantiations of Dijkstra's algorithm. Thus, when the graph is <a href="Sparse_graph" class="mw-redirect" title="Sparse graph">sparse</a>, the total time can be faster than the <a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall algorithm</a>, which solves the same problem in time <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|^{3})}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|^{3})}</annotation>

</semantics>

</math></span><img src="./04ad8b53a2cea864c6d746895cc7397971f72912.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.718ex; height:3.343ex;" alt="{\displaystyle O(|V|^{3})}" loading="lazy"></span>.<sup id="cite_ref-clrs_1-3" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCormenLeisersonRivestStein2001" class="citation cs2"><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a>; <a href="Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2001), <i><a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a></i>, MIT Press and McGraw-Hill, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-262-03293-3</bdi></cite>. Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.</span>

</li>

<li id="cite_note-black-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-black_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-black_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFBlack2004" class="citation cs2">Black, Paul E. (2004), "Johnson's Algorithm", <a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/johnsonsAlgorithm.html"><i>Dictionary of Algorithms and Data Structures</i></a>, <a href="National_Institute_of_Standards_and_Technology" title="National Institute of Standards and Technology">National Institute of Standards and Technology</a></cite>.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFJohnson1977" class="citation cs2"><a href="Donald_B._Johnson" title="Donald B. Johnson">Johnson, Donald B.</a> (1977), "Efficient algorithms for shortest paths in sparse networks", <i><a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>, <b>24</b> (1): <span class="nowrap">1–</span>13, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321992.321993">10.1145/321992.321993</a></span>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207678246">207678246</a></cite>.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFEdmondsKarp1972" class="citation cs2">Edmonds, J.; Karp, Richard M. (1972), "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems", <i><a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>, <b>19</b> (2): <span class="nowrap">248–</span>264, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321694.321699">10.1145/321694.321699</a></cite>.</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFSuurballe1974" class="citation cs2">Suurballe, J. W. (1974), "Disjoint paths in a network", <i>Networks</i>, <b>14</b> (2): <span class="nowrap">125–</span>145, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fnet.3230040204">10.1002/net.3230040204</a></cite>.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/johnson_all_pairs_shortest.html">Boost: All Pairs Shortest Paths</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Graph_and_tree_traversal_algorithms231" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Graph_and_tree_traversal_algorithms231" style="font-size:114%;margin:0 4em"><a href="Graph_traversal" title="Graph traversal">Graph</a> and <a href="Tree_traversal" title="Tree traversal">tree</a> traversal algorithms</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_traversal" title="Graph traversal">Search</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alpha%E2%80%93beta_pruning" title="Alpha–beta pruning">α–β pruning</a></li>

<li><a href="Best-first_search" title="Best-first search">Best-first search</a></li>

<li><a href="Beam_search" title="Beam search">Beam search</a></li>

<li><a href="Bidirectional_search" title="Bidirectional search">Bidirectional search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a>

<ul><li><a href="Lexicographic_breadth-first_search" title="Lexicographic breadth-first search">Lexicographic</a></li>

<li><a href="Parallel_breadth-first_search" title="Parallel breadth-first search">Parallel</a></li></ul></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a>

<ul><li><a href="Iterative_deepening_depth-first_search" title="Iterative deepening depth-first search">Iterative deepening</a></li></ul></li>

<li><a href="Fringe_search" title="Fringe search">Fringe search</a></li>

<li><a href="Jump_point_search" title="Jump point search">Jump point search</a></li>

<li><a href="Monte_Carlo_tree_search" title="Monte Carlo tree search">Monte Carlo tree search</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a></li>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li>

<li><a href="Shortest_path_faster_algorithm" class="mw-redirect" title="Shortest path faster algorithm">Shortest path faster</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka's</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal's</a></li>

<li><a href="Reverse-delete_algorithm" title="Reverse-delete algorithm">Reverse-delete</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><a href="List_of_algorithms#Graph_search" title="List of algorithms">List of graph search algorithms</a></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-22" href="https://en.wikipedia.org/wiki/?title=Johnson's_algorithm&oldid=1296818128">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>